package top.datacluster.basic.algorithm.leetcode.tree;

import top.datacluster.basic.algorithm.leetcode.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class LeetCode102 {

    public List<List<Integer>> levelOrder(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        LinkedList<Integer> level = new LinkedList<>();
        if (root == null){
            return new ArrayList<>();
        }else{
            queue.offerLast(root);
            level.offerLast(1);
        }
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> middle = new ArrayList<>();
        result.add(middle);
        int current = 1;
        while (!queue.isEmpty()){
            int n = level.pollFirst();
            if (n > current){
                middle = new ArrayList<>();
                result.add(middle);
                current = n;
            }
            TreeNode t = queue.pollFirst();
            middle.add(t.val);
            if (t.left != null){
                queue.offerLast(t.left);
                level.offerLast(n + 1);
            }
            if (t.right != null){
                queue.offerLast(t.right);
                level.offerLast(n + 1);
            }
        }
        return result;
    }
}
